#include "xtypes.h"
#include "xaux.h"
#include "xmath.h"
#include "util_vector.h"
#include "util_matrix.h"
#include "util_fractal.h"
#include "util_point.h"
#include <math.h>




CxString ls_fnGenRegStr(lsparam_t lsp, int_t depth)
{
	CxString strForm, strTemp;
	int i, index, length;
	char c;
	
	map<CHAR, CxString> pr;
	vector<CxString> vpr;
	fnSplit(vpr, lsp.strPr, ";");
	
	for(i=0;i<=vpr.size()-1;++i)	//init the map
	{
		pr[vpr[i][0]] = vpr[i].substr(2,vpr[i].size()-2);	
	}
	
	strForm = "";
	strTemp = "";
	
	strForm = lsp.Axiom;
	
	for(i=1;i<=depth;++i)
	{
		length = strForm.length();		
		for(index=0;index<=length-1;index++)
		{
			c = strForm[index];
			switch(c)
			{
			case '+':
			case '-':
			case '[':
			case ']':
				strTemp += c;
				break;
			default:
				strTemp += pr[c];
			}
		}
		strForm = strTemp;
		strTemp = "";
		
	}
	
	return strForm;
}

CxString ls_fnGenRandStr(lsparam_t lsp, int_t depth)
{
	CxString strForm, strTemp;
	int i, index, length;
	char c;
	int random;
	
	vector<CxString> pr;	//ls productions which doesn't contain the left part
	vector<CxString> vpr;
	fnSplit(vpr, lsp.strPr, ";");
	int pr_count = vpr.size();
	for(i=0;i<=pr_count-1;++i)	//init the map
	{
		vpr[i] = xTrimString(vpr[i]);
	}
	
	pr.clear();
	for(i=0;i<=pr_count-1;++i)	//init the map
	{
		pr.push_back(vpr[i].substr(2,vpr[i].size()-2));	//get the production's right
	}
	
	
	strForm = "";
	strTemp = "";
	
	strForm = lsp.Axiom;
	
	for(i=1;i<=depth;++i)
	{		
		length = strForm.length();
		for(index=0;index<=length-1;index++)
		{
			random = (rand())%pr_count;
			c = strForm[index];
			switch(c)
			{
			case '+':
			case '-':
			case '[':
			case ']':
				strTemp += c;
				break;
			default:
				strTemp += pr[random];
			}
		}
		strForm = strTemp;
		strTemp = "";
		
	}
	
	return strForm;
}

void Draw_LS_String(CxSphereCanvas& canvas, CxString str, uint_t xStart, uint_t yStart, int_t len, float_t angle_start, float_t angle)
{
	if(str=="") return;
	
	typedef struct  
	{
		float_t x;
		float_t y;
		float_t dir;
	}knot_t;
	
	int i;
	
	
	knot_t   stack[1024];
	int		stackpushpos;
	for (i = 0 ; i <1024 ; ++i )
	{
		stack[i].x =  0 ;
		stack[i].dir = 0 ;
	}
	stackpushpos = 0 ;
	
	knot_t  mNextKnot ,mCurKnot;
	mCurKnot.x = xStart;
	mCurKnot.y = yStart;
	mCurKnot.dir = angle_start;
	
	int strlength = str.length();
	i = 0;
	
	while(i<strlength)
	{
		switch(str[i])
		{
		case 'F':
			mNextKnot.x = mCurKnot.x  + len * xCos(mCurKnot.dir);
			mNextKnot.y = mCurKnot.y  - len * xSin(mCurKnot.dir);
			mNextKnot.dir = mCurKnot.dir ;
			dda_line(canvas, mCurKnot.x, mCurKnot.y, mNextKnot.x, mNextKnot.y);
			mCurKnot = mNextKnot ;
			break ;
		case '[':
			stack[stackpushpos] = mCurKnot;
			stackpushpos ++;
			break;
		case ']':
			mCurKnot = stack[stackpushpos-1]; 
			stackpushpos -- ;
			break;
		case '+':
			mCurKnot.dir = mCurKnot.dir + angle;
			break;
		case '-':
			mCurKnot.dir = mCurKnot.dir - angle;
			break;
		default:
			;
		}//switch
		++i;
	}//while
	
	return;
	
}

ifsparam_t fnGenIfsParam(CxString strIFS)
{
	ifsparam_t ifs;
	
	if(sizeof(float_t)==sizeof(float))
	{
		sscanf(strIFS.data(), "%f,%f,%f,%f,%f,%f,%f", 
			&(ifs.a), &(ifs.b), &(ifs.c), &(ifs.d), &(ifs.e), &(ifs.f), &(ifs.p));		
		
	}
	else
	{
		sscanf(strIFS.data(), "%lf,%lf,%lf,%lf,%lf,%lf,%lf", 
			&(ifs.a), &(ifs.b), &(ifs.c), &(ifs.d), &(ifs.e), &(ifs.f), &(ifs.p));
	}
	
	
	return ifs;
}

ifsparam_t fnGenIfsParam(CMatrix4x4 mt, float_t probability)
{
	ifsparam_t ifs;
	ifs.a = mt.fnMatrix(0,0);
	ifs.b = mt.fnMatrix(1,0);
	ifs.c = mt.fnMatrix(0,1);
	ifs.d = mt.fnMatrix(1,1);
	ifs.e = mt.fnMatrix(3,0);
	ifs.f = mt.fnMatrix(3,1);
	ifs.p = probability;
	
	return ifs;
}

ifsparam_t fnSetIfsParam(float_t a, float_t b, float_t c, float_t d, float_t e, float_t f, float_t p)
{
	ifsparam_t ifsp;
	ifsp.a = a;
	ifsp.b = b;
	ifsp.c = c;
	ifsp.d = d;
	ifsp.e = e;
	ifsp.f = f;
	ifsp.p = p;
	
	return ifsp;
}


void ExecuteIFS(CxSphereCanvas& canvas, window_t window, TxArray<ifsparam_t> ifs, float_t xstart, float_t ystart, int_t n)
{	
	float x=xstart;
	float y=ystart;
	float newx, newy;
	
	float R;
	int i;
	int ifs_count;
	ifs_count = ifs.Size();
	TxArray<float_t> target_range(ifs_count);
	
	target_range[0] = ifs[0].p;
	for(i=1;i<=ifs_count-1;++i)
	{
		target_range[i] = target_range[i-1]+ifs[i].p;
	}
	target_range[ifs_count-1]=1;	//avoid some bugs
	
	CMatrix4x4 mt;
	mt = fnNormalizeMatrix(window)*fnRasterizationMatrix(fnGen2dViewport(0,0,canvas.GetWidth(), canvas.GetHeight()));
	
	
	while (n > 0)
	{   
		R = xGetRandomF();	
		
		for(i=0;i<=target_range.Size()-1;++i)//get the ifs_code index according to the random no.
		{
			if(R<=target_range[i])
				break;
		}
		
		newx = (ifs[i].a * x) + (ifs[i].b * y) + ifs[i].e;
		newy = (ifs[i].c * x) + (ifs[i].d * y) + ifs[i].f;
		x = newx; y = newy;
		
		point4_t p4d;
		p4d = xGenPoint4(x,y,0,1);
		p4d *= mt;
		
		canvas.SetPixel(p4d.x, p4d.y, 0x00000000);
		n--;
	}
	
	return;	
}




static float_t random_ds(float_t v)
{
	return xGetRandomF_Range(-v, v);
}


static float_t avgEndPoints(TxArray2<float_t>& canvas, int_t x, int_t stride)
{
	return (canvas.GetElement(x-stride, 0) + canvas.GetElement(x+stride, 0))*0.5;
}


static float_t avgSquareVals(TxArray2<float_t>& canvas, int_t x, int_t y, int_t stride)
{
    return (canvas.GetElement(x-stride, y-stride) + canvas.GetElement(x+stride, y-stride)
		+ canvas.GetElement(x-stride, y+stride) + canvas.GetElement(x+stride, y+stride))*0.25;
	
}

static float_t avgDiamondVals(TxArray2<float_t>& canvas, int_t x, int_t y, int_t stride)
{
    if (y == 0)
		return (canvas.GetElement(x-stride, y) + 2*canvas.GetElement(x, y+stride)
		+ canvas.GetElement(x+stride, y))*0.25;
    else if (y == canvas.GetLimitY()-1)
		return (canvas.GetElement(x-stride, y)
		+ canvas.GetElement(x+stride, y) + 2*canvas.GetElement(x, y-stride))*0.25;
    else if (x == 0)
		return (canvas.GetElement(x, y+stride)
		+ 2*canvas.GetElement(x+stride, y) + canvas.GetElement(x, y-stride))*0.25;
    else if (x == canvas.GetLimitX()-1)
		return (2*canvas.GetElement(x-stride, y) + canvas.GetElement(x, y+stride)
		+ canvas.GetElement(x, y-stride))*0.25;
    else
		return (canvas.GetElement(x-stride, y) + canvas.GetElement(x, y+stride)
		+ canvas.GetElement(x+stride, y) + canvas.GetElement(x, y-stride))*0.25;
}



void Do1DFractalFill(TxArray2<float_t>& canvas, int_t iterations, float_t initial_value, float_t H)
{
	int_t size_segment=pow(2.0f,iterations)+1;
	if(size_segment%2!=1 || size_segment==1) return;	//It's not allowed that size_segment is a even number or 1
	canvas.SetCaps(size_segment, 1);
	canvas.Clear(0.);
	
	int_t	x;
    int_t	stride;
    int_t	size_sub;
	float_t	ratio, scale;
	
	
	size_sub = size_segment-1;
	
	ratio = (float_t)pow(2.0f,-H);
	scale = ratio;
	
	stride = size_sub / 2;
    canvas.SetElement(0,		0,			initial_value);
	canvas.SetElement(size_sub,	0,			initial_value);
	
	while (stride)
	{
		for (x=stride; x<=size_sub-stride; x+=2*stride)
		{
			canvas.SetElement(x,0, scale * random_ds(.5) + avgEndPoints(canvas, x, stride));
		}
		
		scale *= ratio;
		stride >>= 1;		
	}//while (stride)
	
	return;
}


void Do2DFractalFill(TxArray2<float_t>& canvas, int_t iterations, float_t initial_value, float_t H)
{
	int_t size_square=pow(2.0f,iterations)+1;
	if(size_square%2!=1 || size_square==1) return;	//It's not allowed that size_square is a even number or 1
	canvas.SetCaps(size_square, size_square);
	canvas.Clear(0.);
	
	int_t	x, y;
    int_t	stride;
    int_t	size_sub;
	float_t	ratio, scale;
	
	
	size_sub = size_square-1;
	
	
	
	ratio = (float_t)pow(2.0f,-H);
	scale = ratio;
	
	stride = size_sub / 2;
    canvas.SetElement(0,		0,			initial_value);
	canvas.SetElement(0,		size_sub,	initial_value);
	canvas.SetElement(size_sub,	0,			initial_value);
	canvas.SetElement(size_sub,	size_sub,	initial_value);
	
	
	while (stride)
	{
		
		//do square
		for (y=stride; y<=size_sub-stride; y+=2*stride)
		{
			for (x=stride; x<=size_sub-stride; x+=2*stride)
			{
				canvas.SetElement(x,y, scale * random_ds(.5) + avgSquareVals(canvas, x, y, stride));
			}
		}
		
		//do diamond
		for (y=stride; y<=size_sub-stride; y+=2*stride)
		{
			for (x=stride; x<=size_sub-stride; x+=2*stride)
			{
				
				canvas.SetElement(x-stride, y, scale * random_ds(.5) + avgDiamondVals(canvas, x-stride, y, stride));
				canvas.SetElement(x+stride, y, scale * random_ds(.5) + avgDiamondVals(canvas, x+stride, y, stride));
				canvas.SetElement(x, y-stride, scale * random_ds(.5) + avgDiamondVals(canvas, x, y-stride, stride));
				canvas.SetElement(x, y+stride, scale * random_ds(.5) + avgDiamondVals(canvas, x, y+stride, stride));
			}
		}
		
		
		scale *= ratio;
		stride >>= 1;
		
		
	}//while
	
	
	
	
	return;
}


void fnSplit(vector<CxString> & v, const CxString& src, CxString delimit, CxString null_subst)
{
	if( src.empty()||delimit.empty() ) throw "split: empty CxString\0";
	
	v.clear();
	int_t deli_len = delimit.size();
	
	long index = 0, last_search_position =0;
	while( (index=src.find(delimit,last_search_position))!=-1 )//loop while it can fine the delimit
	{
		if(index==last_search_position)
			v.push_back(null_subst);
		else
			v.push_back( src.substr(last_search_position, index-last_search_position) );
		
		last_search_position = index + deli_len;
	}
	CxString last_one = src.substr(last_search_position, src.size()-last_search_position);
	v.push_back( last_one.empty()? null_subst:last_one );

	return;
}



